This invention relates to a buffer management system and more particularly to such a system for a high speed packet network supporting multipoint connections with multiple transmitters operating over channels at different rates. Various techniques have been devised t prevent buffer overload and the loss of data or packets. The present invention is directed to a mechanism for determining which packets are to be discarded in the event of an overload.
One of the principal advantages of packet switching is the ability to support communication channels of any rate across a potentially wide range. Not only can different channels operate at different rates, but the rates of individual channels may vary over time. This latter property leads to the possibility of overload as there may be periods when the total offered traffic exceeds the network's capacity.
In conventional low speed packet networks such overload periods are controlled using a variety of feed-back oriented techniques which attempt to detect overload and then apply control mechanisms that reduce the overload In high speed networks, for example, networks that transmit at 100 megabits/sec., these techniques are more difficult to implement and less effective because the onset of overload is very rapid relative to the time it takes to exert control. This has led to the development of control strategies which attempt to limit the likelihood of overload in the first place by allocating network resources based on application requirements and blocking new connections whenever the required resources are unavailable. On those occasions when local overloads occur, the network reacts by discarding packets.
In networks supporting only point-to-point or multipoint connections involving a single transmitter, such overloads can be made to occur rarely enough to obviate the need for additional controls. However in networks supporting general multipoint connections additional mechanisms are needed. The present invention addresses the problem of how a network of this type, having general multipoint connections, selects which packets to discard or drop when an overload occurs.
The buffer management system of the present invention is used in a broadcast packet switching network as generally shown and described in said copending application. The packet switching network generally comprises an array of packet switches, which switches are generally connected by one or more high bit rate data links. Virtual circuits passing through a plurality of packet switches are set up in the network to provide single point as well as multipoint connections. This enables a wide range of commercial services including television distribution and conferencing. The basic switching capability of the network is provided by a packet switching module. The switching modules can be interconnected to form packet switches which, in turn, may be interconnected to form the packet switching network. Such a network is shown and described in said copending application.
As explained in the copending application, each of the switch modules comprises a copy network, a set of broadcast and group translators, a distribution network and a routing network. Broadcast packets are replicated in the copy network. Each copy of a broadcast packet that leaves the copy network is provided with a destination address by one of the broadcast and group translators. The distribution and routing networks then route the packet copies to their destinations. A method for adding or deleting destinations from a given broadcast channel is provided.
Buffers are associated with the packet processors at both the input and output links of the switch fabric. While packets may be buffered at the input links and within the switch fabric itself, in accordance with the buffer management system of the present invention the bulk of the queueing takes place in the output link buffers. Further in accordance with the invention in order to determine which packets are to be dropped in an overload condition, each connection or group of connections, whether single point or multipoint, is allocated a bandwidth, and is further allocated a number of buffer slots in the output link buffer in proportion to the allocated bandwidth. For example, if a given connection or channel is allocated 20% of the bandwidth on a given link, then it is also allocated 20% of the buffer slots in that link's output buffer. If the link buffer is not full then the allocation has no effect. However, if the buffer becomes full, the buffer allocation is used to determine which packets are discarded. Connections using more than their allocated buffer slots lose packets during overload while connections that are operating within their allocation are protected, that is, do not lose packets.
Hence, the system of the present invention generally includes a network associated with each packet processor for identifying or "marking" a packet as an "excess packet" when a packet for a particular connection is received at the output link buffer of that packet processor and the buffer slots allocated to that connection are filled. The system further comprises a buffer implementation network that maintains packet ordering but discards excess packets first in an overload condition. The buffer implementation network includes a memory array or RAM in which the packets are stored in columns, and suitable input and output shift registers for transferring the packets into and out of the memory array. The buffer implementation network further includes a status network that maintains information about the packets stored in each column of the memory array. It supports writing to and reading from the buffer implementation network of the packet processor in a selected order, and also controls the writing to a memory column with a priority depending on whether the incoming packet is or is not an excess packet and further whether or not the memory column is occupied by an excess packet. Hence, with this invention nonexcess packets are protected, nonexcess packets have priority over excess packets, and yet excess packets will be written into the buffer (not dropped) as long as slots are available in the buffer. Once written into memory an excess packet will be transmitted unless the buffer becomes full and a nonexcess packet takes priority.
Hence, a primary advantage of the present invention is that the storage capacity of the output link buffer of each packet processor is most efficiently utilized to receive, store, and transmit packets, and only when overloaded will excess packets be lost with nonexcess packets protected.